МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
СПИСКИ, СТЕКИ, ЧЕРГИ, КІЛЬЦЯ
В МОВІ ПРОГРАМУВАННЯ С
Інструкція
до лабораторної роботи № 13
з курсу “Проблемно-орієнтовані мови програмування”
для студентів базового напрямку 6.08.04
"Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
Системи автоматизованого проектування
Протокол № 1 від 22.08.2011 р.
ЛЬВІВ 2011
1. МЕТА РОБОТИ
Мета роботи - навчитися використовувати динамічний розподіл пам’яті для роботи зі списками, чергами і кільцями.
2. СПИСКИ. СТЕКИ, ЧЕРГИ, КІЛЬЦЯ
Список - це набір елементів (найчастіше структурних змінних), розташованих у динамічній пам'яті й зв'язаних між собою з вказівниками на ці елементи. Спосіб зв'язку елементів, який застосовується, визначає тип списку.
Списки бувають лінійними й кільцевими, однозв'язними й двозв’язними. Елемент однозв'язного списку містить крім безпосередньо "корисної" інформації також інформацію про наступний або попередній елемент списку. Відповідно елемент двозв’язного списку містить інформацію, як про наступний, так і про попередні елементи. Останній елемент кільцевого списку містить вказівник на перший елемент списку.
Якщо список розташовується в оперативній пам'яті, то інформація для пошуку наступного об'єкта - адреса (вказівник) у пам'яті. Якщо зв'язний список зберігається у файлі на диску, то інформація про наступний елемент може включати зсув елемента від початку файлу, положення вказівника запису/зчитування файлу, ключ запису або будь-яку іншу інформацію, що дозволяє однозначно відшукати наступний елемент списку.
Графічно списки можна відобразити в такий спосіб:
Однозв'язний Двозв’язний Однозв'язний
кільцевий список
лінійний список лінійний список
Найпоширенішими випадками лінійного однозв'язного списку служать черга й стек.
Черга - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в кінець списку, а вибираються для обробки строго з початку. Принцип організації черги можна описати так: "першим прийшов - першим пішов" (FІFO - Fіrst Іn, Fіrst Out). Черга елементів може бути реалізована з використанням масивів, зв'язного списку або іншим способом. Щоб не обмежувати максимальне число елементів у черзі, найбільше доцільно її побудова у вигляді однозв'язного списку. Додавання нових елементів відбувається завжди в кінець списку (в "хвіст"). Останній елемент позначається особливим чином, наприклад поле вказівника на наступний елемент дорівнює NULL. Рекомендується при роботі із чергою використовувати два вказівники: один - на початок черги, а другий -на її кінець. Це спростить як вибір елементів із черги, так і їхнє додавання.
Стек - це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго в початок списку й вибираються для обробки також строго з початку списку (за принципом "першим прийшов - останнім пішов" (FІLO - Fіrst Іn, Last Out), тобто перший занесений у стек елемент буде оброблений останнім).
/* Приведемо приклад програми, в якій реалізований список (стек) осіб (ПІП) і відповідної їм інформації. Також у програмі реалізовані базові операції роботи зі списками. */
#іnclude<stdіo.h>
#іnclude<stdlіb.h>
#іnclude<strіng.h>
#іnclude<conіo.h>
#іnclude<іostream.h>
struct MAN // Структура, що описує особу
// Прізвище, Ім'я, По батькові, Дата народження
{ char F[15],
I[15],
O[15[/
DN[10];
};
struct // Структура елемента стека
{ struct MAN M;
struct STACK *next;
};
// Oпис функцій
voіd add (struct STACK **head); /* Додавання елемента в стек */
іnt іden(struct STACK head,struct MAN w); /* Перевіряє наявність елемента */
voіd іnput(struct MAN *w); /* Ввід інформації про особу */
voіd dіsplay(struct STACK"*wk); /* Вивід вмістимого стека */
struct STACK *prіnt(struct STACK *h); /* Вивід на екр...
